class Node:
    def __init__(self):
        self.chilren = [None] * 26
        self.isEnd = False

class WordDictionary:

    def __init__(self):
        self.root = Node()

    def addWord(self, word: str) -> None:
        node = self.root   # 从根节点开始构造这个word对应的路径节点
        for char in word:
            # 将当前字符添加到当前节点对应的子节点位置，然后递归更新
            id_ = ord(char) - ord('a')
            if not node.chilren[id_]:
                node.chilren[id_] = Node()
            node = node.chilren[id_]
        node.isEnd = True # 最后一个节点的isEnd置为true，表示一个完整的字符串
            

    def search(self, word: str) -> bool:
        return self.__dfs_search(word, 0, self.root) # 从根节点开始匹配word[0]


    """
    回溯法查找字典树是否匹配word
     @param word: 待匹配字符串
     @param idx: 当前匹配word[idx]字符
     @param node: 搜索待匹配字符是否存在的节点
    """
    def __dfs_search(self, word:str, idx: int, node: Node) ->bool:
        if idx == len(word):
            return node.isEnd  # 字符匹配结束，返回当前节点是否为尾节点
        if word[idx] == '.':
             # 当前字符为.，匹配任意字符，即枚举所有非空子节点去匹配下一个字符
             for child in node.chilren:
                if child and self.__dfs_search(word, idx + 1, child):
                    return True
        else:
            # 获取当前字符对应的子节点
            child = node.chilren[ord(word[idx]) - ord('a')]
            if child and self.__dfs_search(word, idx + 1, child):
                return True
        return False



# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)